package com.hqq.exercise.recursion_loop;

import com.hqq.exercise.tree.BinaryTreeNode;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * TransferConclusion 递归和循环转换总结
 * 1.直接转化
 * 消除尾递归和单向递归
 * [尾递归]
 * 指在递归算法中递归调用语句只有一个 且处于算法的最后
 * 对于尾递归形式的递归算法 转换成循环时无需用stack保存中间结果
 * [单向递归]
 * 多处递归调用 但是递归之间没有直接的关系 并且这些递归都处于算法的最后
 * 2.间接转换法
 * 使用栈保存中间结果
 * 二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现
 * 使用方法一般是:
 * 初始状态s0入栈
 * whle(栈不为空){
 *      退栈 栈顶元素赋给s
 *      if(s是要找的元素)
 *          返回s;
 *      else{
 *          找到s的相关状态s1
 *          s1入栈
 *      }
 * }
 * Created by heqianqian on 2017/8/23.
 */
public class TransferConclusion {

    private static BinaryTreeNode root;

    static {
        BinaryTreeNode leftChild = new BinaryTreeNode(4);
        leftChild.leftNode = new BinaryTreeNode(2);
        leftChild.rightNode = new BinaryTreeNode(3);

        BinaryTreeNode rightChild = new BinaryTreeNode(6);
        rightChild.leftNode = new BinaryTreeNode(5);
        rightChild.rightNode = new BinaryTreeNode(7);

        root = new BinaryTreeNode(11);
        root.leftNode = leftChild;
        root.rightNode = rightChild;
    }

    /**
     * 尾递归
     */
    private static int factorialByRecurision(int num) {
        if (num == 1) {
            return 1;
        }
        return num * factorialByRecurision(num - 1);
    }

    private static int factorialByLoop(int num) {
        int result = 1;
        for (int i = 2; i <= num; i++) {
            result *= i;
        }
        return result;
    }

    private static int fibonacciByRecursion(int num) {
        if (num == 1 || num == 2) {
            return 1;
        }
        return fibonacciByRecursion(num - 1) + fibonacciByRecursion(num - 2);
    }

    private static int fibonacciByLoop(int num) {
        if (num == 1 || num == 2) {
            return 1;
        }
        int s1 = 1, s2 = 1;
        int result = 0;
        for (int i = 3; i <= num; i++) {
            result = s1 + s2;
            s1 = s2;
            s2 = result;
        }
        return result;
    }

    /**
     * 递归遍历树 [先序遍历]
     *
     * @param root
     */
    public static void traversalTreeByRecursion(BinaryTreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value + " ");
        traversalTreeByRecursion(root.leftNode);
        traversalTreeByRecursion(root.rightNode);
    }


    public static void traversalTreeByLoop(BinaryTreeNode root) {
        //使用栈
        Stack<BinaryTreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            BinaryTreeNode temp = stack.pop();
            System.out.print(temp.value + " ");
            if (temp.rightNode != null) {
                stack.push(temp.rightNode);
            }
            if (temp.leftNode != null) {
                stack.push(temp.leftNode);
            }
        }
    }

    public static void traversalTreeByLoop2(BinaryTreeNode root) {
        //使用栈
        Queue<BinaryTreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            BinaryTreeNode temp = queue.poll();
            System.out.print(temp.value + " ");
            if (temp.leftNode != null) {
                queue.add(temp.leftNode);
            }
            if (temp.rightNode != null) {
                queue.add(temp.rightNode);
            }
        }
    }


    public static void main(String[] args) {
        /*直接转换法*/
        //1.尾递归
        int result = fibonacciByRecursion(7);
        System.out.println(result);
        result = fibonacciByLoop(7);
        System.out.println(result);

        //2.单向递归
        int factorial = factorialByRecurision(4);//4*3*2*1 = 24
        System.out.println(factorial);
        factorial = factorialByLoop(4);//4*3*2*1 = 24
        System.out.println(factorial);


        /*间接转换法*/
        traversalTreeByRecursion(root);
        System.out.println();
        traversalTreeByLoop(root);
        System.out.println();
        traversalTreeByLoop2(root);
    }

}
